package Tree_09.AvlTree_08;

/*
 * @Author 罗
 * @date 2020/3/27 - 9:04 上午
 *
 */

import Tree_09.BinarySortTree_07.BinarySortTree;
import Tree_09.BinarySortTree_07.NodeForBinarySortTree;

public class AvlTree extends BinarySortTree {

    public void addToAvl(NodeForBinarySortTree node) {
        if (getRoot() == null) {
            setRoot(node);
            return;
        }
        addForAvlTree(node, getRoot());

    }

    /**
     * 双旋转的添加节点
     * @param node
     * @param temp
     */
    private void addForAvlTree(NodeForBinarySortTree node, NodeForBinarySortTree temp) {
        if (node.getValue() < temp.getValue()) {
            if (temp.getLeft() == null) {
                temp.setLeft(node);
            } else {
                addForAvlTree(node, temp.getLeft());
            }
        } else {
            if (temp.getRight() == null) {
                temp.setRight(node);
            } else {
                addForAvlTree(node, temp.getRight());
            }
        }
        /*
         * 右子树高度-左子树高度>1，需要左旋
         *   左旋：把根节点的第一个右节点的左子树 拆除 并放到 根节点的第一个左节点的右指针上
         * 从而降低右子树的高度
         * 本质是把根节点的右节点的左子树移动
         *      但是如果根节点的右节点的左子树高度  >  根节点的右节点的右子树
         *          根节点的右节点的左子树就会被移动到 根节点的左节点的右指针上，
         *          高度差没有减小，从而无法构成平衡二叉树
         *      解决办法：在把根节点的右节点的左子树（较高）移动之前，
         *              先把根节点的右节点进行右旋，从而将
         *              根节点的右节点的左右子树高度差缩小，再把根节点的右节点的左子树移动
         *      执行解决办法之前，需要判断根节点的右节点是否为null
         *             但是也可以不判null，因为 getLeftSonTreeHigh(),getRightSonTreeHigh()
         *              方法里将空节点的树高返回为-1
         *              -1>-1不成立 所以不用写null指针判断
         * */
        if (getRightSonTreeHigh(temp) - getLeftSonTreeHigh(temp) > 1) {
            /*
             * 解决办法的执行
             *
             * */
            if (getLeftSonTreeHigh(temp.getRight()) > getRightSonTreeHigh(temp.getRight())) {
                /*
                 * 根节点的右节点的左子树 高度 >  根节点的右节点的右子树
                 * 先把根节点的右子树左旋
                 * */
                rightRotate(temp.getRight());
            }

            leftRotate(temp);
            /*
             * 已经旋转过一次了，再次旋转也没有意义
             * 提高效率
             *
             * */
            return;
        }
        /*
         * 左子树高度-右子树高度>1，需要右旋
         *   右旋：把根节点的第一个左节点的右子树 拆除 并 放在根节点的第一个右节点的左指针上
         * 从而降低左子树的高度
         * 本质是把根节点的左节点的右子树移动
         *      但是如果根节点的左节点的右子树高度  >  根节点的左节点的左子树
         *          根节点的左节点的右子树就会被移动到 根节点的右节点的左指针上，
         *          高度差没有减小，从而无法构成平衡二叉树
         *      解决办法：在把根节点的左节点的右子树（较高）移动之前，
         *              先把根节点的左节点进行左旋，从而将
         *              根节点的左节点的左右子树高度差缩小，再把根节点的左节点的右子树移动
         *      执行解决办法之前，需要判断根节点的右节点是否为null
         *             但是也可以不判null，因为 getLeftSonTreeHigh(),getRightSonTreeHigh()
         *              方法里将空节点的树高返回为-1
         *              -1>-1不成立 所以不用写null指针判断
         * */
        if (getLeftSonTreeHigh(temp) - getRightSonTreeHigh(temp) > 1) {

            if (getRightSonTreeHigh(temp.getLeft()) > getLeftSonTreeHigh(temp.getLeft())) {

                leftRotate(temp.getLeft());
            }
            rightRotate(temp);
        }
    }

    /**
     * 左子树高度-右子树高度>1，需要右旋
     * 右旋：把根节点的第一个左节点的右子树 拆除 并 放在根节点的第一个右节点的左指针上
     * 从而降低左子树的高度
     * <p>
     * node的左节点的值小于 node左节点的右节点，且小于根节点
     *
     * @param node
     */
    private void rightRotate(NodeForBinarySortTree node) {
        /*
         * 创建一个新的右子树节点，值和根节点的值一样
         * */
        NodeForBinarySortTree rightSonTreeNew = new NodeForBinarySortTree(node.getValue());
        /*
         * 新节点的右指针指向根节点的右子树
         * */
        rightSonTreeNew.setRight(node.getRight());
        /*
         * 新节点的左指针指向根节点的左子树的右节点
         * */
        rightSonTreeNew.setLeft(node.getLeft().getRight());
        /*
         * 将根节点指向新节点
         * */
        node.setRight(rightSonTreeNew);
        /*
         * 设置根节点的值为根节点的左节点
         * */
        node.setValue(node.getLeft().getValue());
        /*
         * 至此根节点的左节点已经被拆解完毕
         * 把根节点的左指针指向根节点的左节点的做节点
         * */
        node.setLeft(node.getLeft().getLeft());
    }


    /**
     * 右子树高度-左子树高度>1，需要左旋
     * 左旋：把根节点的第一个右节点的左子树 拆除 并放到 根节点的第一个右节点的左指针上
     * 从而降低右子树的高度
     * <p>
     * <p>
     * 1.把传入的节点的右子树的左子树拆到根节点的新创建的左子树的右指针
     * 新创建的左子树的左指针指向原来的左子树
     * 2.传入节点的右子树指向，原根节点的右子树的右子树
     * 3.到此原根节点的第一个右节点，已经被拆解完毕，但是原根节点的第一个右节点的值还没有解决
     * 把原根节点的右节点的值赋值给根节点
     * 因为，根节点的第一个右节点一定大于根节点，也一定大于根节点右节点的左节点
     *
     * @param node 传入的节点将被视作左旋的根节点
     */
    private void leftRotate(NodeForBinarySortTree node) {

        /*
         * 创建一个和当前根节点的值相等的节点
         * */
        NodeForBinarySortTree leftSonTreeNew = new NodeForBinarySortTree(node.getValue());
        /*
         * 把新创建的节点的左指针指向原根节点的左子树
         * */
        leftSonTreeNew.setLeft(node.getLeft());
        /*
         * 把新创建的节点的右指针指向原根节点的右子树的左子树
         *   不是找最小值
         * 因为原根节点的右子树的任何节点都要比根节点的值大
         * 根节点的右子树的左子树更是如此
         *
         * */
        leftSonTreeNew.setRight(node.getRight().getLeft());
        /*
         * 把原根节点的左指针指向新创建的左子树
         * */
        node.setLeft(leftSonTreeNew);
        /*
         * 把原根节点的第一个右节点的值 赋值给原节点
         * */
        node.setValue(node.getRight().getValue());
        /*
         * 把根节点的右指针指向右子树的右子树
         * */
        node.setRight(node.getRight().getRight());
    }


    /**
     * 获取以该节点的左节点作为根节点，树的高度
     *
     * @param node
     * @return
     */
    public int getLeftSonTreeHigh(NodeForBinarySortTree node) {
        if (node == null) {
            return -1;
        }
        return getTreeHigh(node.getLeft());
    }

    public int getRightSonTreeHigh(NodeForBinarySortTree node) {
        if (node == null) {
            return -1;
        }

        return getTreeHigh(node.getRight());
    }


    /**
     * 获得以当前节点作为根节点，这棵树的高度
     *
     * @param node
     * @return
     */
    public int getTreeHigh(NodeForBinarySortTree node) {
        if (node == null) {
            return 0;
        }
        /*
         * Math.max()之后要+1，因为max()只是调用了递归，而+1才是把树的高度返回
         *  +1:每一层只能+1的高度
         * */
        return Math.max(node.getLeft() == null ? 0 : getTreeHigh(node.getLeft()),
                node.getRight() == null ? 0 : getTreeHigh(node.getRight())) + 1;
    }
}
